# Поиск

Поиск часто используется в повседневной жизни, а также в компьютерных науках. 
Если мы выполняем ручной поиск, то, скорее всего, пытаемся сопоставить изображение или описание, 
которое есть в нашем мозгу, с искомым реальным объектом. 
Таким образом, это своего рода операция сопоставления с образцом. 
Точно так же сопоставление с образцом является распространенным методом, используемым в вычислениях. 

## Линейный поиск

**Алгоритм:**

[Линейный, последовательный поиск](https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA) — 
алгоритм нахождения заданного значения произвольной функции на некотором отрезке.

**Оценка:**

- **Время**:
    - Худшее - \\(O(n)\\)
    - Лучшее - \\(O(1)\\)
    - Среднее - \\(O(n)\\)
- **Память** - \\(O(1)\\)

**Код:**

```dotty
@tailrec
def linearSearch[A](list: List[A], key: A): Option[A] =
  list match
    case Nil                      => None
    case head :: _ if head == key => Some(key)
    case _ :: tail                => linearSearch(tail, key)

val text   = "This is a functional implementation."
linearSearch(text.toList, 'a')  
// Some(a)
```

## Бинарный поиск

**Алгоритм:**

[Двоичный (бинарный) поиск](https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA) 
(также известен как **метод деления пополам** или **дихотомия**) — 
классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины.

**Оценка:**

- **Время**:
    - Худшее - \\(O(n)\\)
    - Лучшее - \\(O(1)\\)
    - Среднее - \\(O(n)\\)
- **Память** - \\(O(1)\\)

**Код:**

```dotty
def binarySearch[A: Ordering](list: List[A], key: A): Option[A] =
  def search(l: List[A], r: List[A]): Option[A] =
    if l == r then None
    else test(l, r, middle(l, r))

  def test(l: List[A], r: List[A], m: List[A]): Option[A] =
    if key < m.head then search(l, m)
    else if key > m.head then search(m.tail, r)
    else Some(m.head)

  def middle(l: List[A], r: List[A]): List[A] =
    @tailrec
    def race(t: List[A], h: List[A]): List[A] =
      if h != r && h.tail != r then
        race(t.tail, h.tail.tail)
      else t

    race(l, l.tail)

  search(list, Nil)
end binarySearch

binarySearch((1 to 100).toList, 45)
// Some(45)
```

## Алгоритм выбора

**Алгоритм:**

[Линейный (в среднем) алгоритм для нахождения k-й порядковой статистики](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%B0)

Алгоритм для нахождения k-й порядковой статистики, основанный на алгоритме быстрой сортировки и работающий за O(n) в среднем.

Идея алгоритма заключается в том, что массив разбивается на две части относительно случайно (равновероятно) 
выбранного элемента — в одну часть попадают элементы, меньшие, чем выбранный, 
в другую — остальные (эта операция выполняется за O(n), 
по её окончании выбранный элемент находится в позиции `j`. 
Если в первой части оказалось ровно `k-1` элементов (`j = k`), то выбранный элемент является искомым, 
если `j > k`, то алгоритм выполняется рекурсивно для первой части массива, 
иначе — для второй (в последнем случае для следующей итерации от `k` отнимается `j`).

**Оценка:**

- **Время**:
    - Худшее - \\(O(n^{2})\\)
    - Лучшее - \\(O(1)\\)
    - Среднее - \\(O(n)\\)
- **Память** - \\(O(1)\\)

**Код:**

```dotty
def selectionSearch[A: Ordering](list: List[A], n: Int): Option[A] =
  @tailrec
  def partitionAndSearch(as: List[A], m: Int): Option[A] = as match
    case Nil => None
    case h :: t =>
      val (l, p, g) = partition(h, t)
      val len       = l.length
      if len == m - 1 then Some(p)
      else if len >= m then partitionAndSearch(l, m)
      else partitionAndSearch(g, m - len - 1)

  def partition(head: A, tail: List[A]): (List[A], A, List[A]) =
    @tailrec
    def loop(
        rest: List[A],
        less: List[A],
        p: A,
        more: List[A]
    ): (List[A], A, List[A]) =
      rest match
        case Nil             => (less, p, more)
        case h :: t if h < p => loop(t, h :: less, p, more)
        case h :: t          => loop(t, less, p, h :: more)

    loop(tail, Nil, head, Nil)

  if n <= 0 then None
  else partitionAndSearch(list, n)
end selectionSearch

selectionSearch((1 to 100).toList, 45)
// Some(45)
```

## Поиск подстроки

В текстовом сопоставлении поиск подстроки - очень распространенное требование. 
Если мы выполняем поиск подстроки вручную, то сопоставляем первый символ искомой подстроки с первым символом текста, 
в котором выполняем сопоставление. 
Если совпадает, то продолжаем со вторым символом и так далее. 
Поскольку мы можем перемещать взгляд, то мы могли бы начать с сопоставления с середины страницы 
или с любого места, которое нам нравится. 
Но если мы ищем первое вхождение, то это будет последовательное совпадение или поиск. 
В случае компьютеров сопоставление обычно выполняется последовательно. 
Но это можно изменить, если есть другие требования. 

Поиск может осуществляться широким спектром алгоритмов. 
Ниже рассмотрим несколько алгоритмов: алгоритм наивного поиска и алгоритм поиска Кнута-Морриса-Пратта.

### Алгоритм наивного поиска

**Алгоритм:**

- Для первого символа в тексте выполните следующий цикл сопоставления.
    - Сопоставьте первый символ искомой подстроки с текущим символом текста
    - Если есть совпадение, то сопоставьте второй символ подстроки со следующим символом текста.
      Продолжайте до тех пор, пока все символы подстроки не совпадут с символами текста. 
      Если есть полное совпадение, верните индекс текущего символа текста, который в данном случае равен `0`. 
    - Если совпадения нет, выйдите из этого цикла сопоставления.
- Теперь переместите указатель на второй символ текста и продолжите выполнение цикла сопоставления, описанного выше. 
   Любое частичное совпадение теряется в процессе поиска с возвратом. 
   Если есть полное совпадение, вернуть индекс, который в данном случае равен `1`. 
   Если полного совпадения нет, переместите указатель на третий символ. 
- Продолжаем описанные выше шаги, пока не достигнем индекса, который при добавлении к длине подстроки дает длину текста, 
   т.е. за последней начальной точкой сравнения должно следовать достаточное количество символов, 
   чтобы индекс оставался в пределах ограничения. 
   В худшем случае сложность времени выполнения наивного поиска составляет _O(mn)_, 
   где _m_ — длина искомой подстроки, а _n_ — длина текста, в котором выполняется поиск.

**Оценка:**

- **Время** - O(mn)
- **Память** - ???

**Код:**

```dotty
def naiveSubstringSearch(searchWord: String, source: String): Int =
  (0 to (source.length - searchWord.length))
    .find: i =>
      searchWord.indices.forall: j => 
        source(j + i) == searchWord(j)
    .getOrElse(-1)
```

**Метрики:**

Поиск подстроки в 100 символов в тексте в миллион символов занимает 0,2 секунды.

```dotty
private val source: String = Random.nextString(1_000_000)
private val searchWord: String = source.takeRight(100)

@main def searchBench(): Unit =
  println(naiveSubstringSearch(searchWord, source))
  println(kmpSubstringSearch(searchWord, source))
      
// CPU Time: 169 ms
// Allocation memory size: 120,31 MB      
```

### Алгоритм поиска Кнута-Морриса-Пратта

**Алгоритм:**

- Инициализировать переменные. 
    - `m` = длина шаблона (искомая подстрока) 
    - `n` = длина текста 
    - `T` = таблица префиксов 
    - `i` = количество совпадающих символов 
- Сначала вычислите таблицу префиксов. Это препроцесс, который обрабатывает шаблон, чтобы найти совпадения префиксов шаблона с самим шаблоном. 
  Образец здесь представляет собой подстроку для поиска. 
  Он указывает, какая часть последнего сравнения может быть повторно использована, если сравнение не удалось; 
  это улучшение по сравнению с алгоритмом наивного поиска. 
  `P` и `S` обозначают шаблон для поиска и текст, в котором выполняется поиск, соответственно. 
  Функция префикса определяется как размер наибольшего префикса `P[0,1,...,l−1]`, который также является суффиксом `P[1,2,...,l]`. 
  Таблица префиксов вычисляется с помощью следующей подпрограммы, которая имеет сложность времени выполнения _O(m)_.
  ```text
  a. m ← length[P]
  b. T[1] ← 0
  c. k ← 0
  d. for l ← 2 to m do
       while k > 0 and P[k + 1] != p[l] do
         k ← T[k]
       end while
       if P[k + 1] = P[l] then
         k ← k + 1
       end if
       T[l] ← k
     end for
  e. return T
  ```
- Выполните инициализацию переменной: `i = 0` указывает на начало совпадения. 
- Сравнить первый символ искомой подстроки (образца) с первым символом текста. 
  Если это не совпадение, замените значение `T[i]` на `i`. Если это совпадение, увеличьте значение `i` на `1`. 
- Затем проверьте, все ли элементы шаблона совпадают с текстовыми элементами. 
  Если не совпадают, повторите процесс поиска. Если совпало, верните начальный индекс совпадающей подстроки текста. 
- Продолжайте описанные выше шаги, чтобы найти следующее совпадение. 
- Вышеуказанные шаги могут быть представлены следующим псевдокодом:
  ```text
  a. n ← length[S]
  b. m ← length[P]
  c. T ← computePrefixTable(P), вызвать подпрограмму вычисления префикса выше.
  d. i ← 0
  e. for j ← 1 to n do
       while i > 0 and P[i + 1] != S[j] do
         i ← T[i]
         if P[i + 1] = S[j] then
           i ← i + 1
         end if
         if i = m then
           i ← P[i]
         end if
       end while
     end for
  ```
- Возвращает набор начальных индексов для всех совпадающих подстрок текста. 
  Сложность времени выполнения вычисления таблицы префиксов составляет _O(m)_. 
  Для сравнения шаблона с текстом требуется _O(n)_. 
  Следовательно, общая сложность времени выполнения составляет _O(m+n)_.

Чтобы пояснить приведенный выше алгоритм, давайте вычислим таблицу префиксов для `P = {xyxyxzx}`. 
Первоначально `m = length[P] = 7`, `T[1] = 0` и `k = 0`. 
Как показано в приведенном выше алгоритме, `m` — это длина искомого шаблона или строки, 
`T` — таблица префиксов и `k` — начальное значение потенциала, которое инициализируется `0`.

**Шаг 1**: `l = 2`, `k = 0`, `T[2] = 0`

| l | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| P | x | y | x | y | x | z | x |
| T | 0 | 0 |   |   |   |   |   |


**Шаг 2**: `l = 3`, `k = 0`, `T[3] = 1`

| l | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| P | x | y | x | y | x | z | x |
| T | 0 | 0 | 1 |   |   |   |   |


**Шаг 3**: `l = 4`, `k = 1`, `T[4] = 2`

| l | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| P | x | y | x | y | x | z | x |
| T | 0 | 0 | 1 | 2 |   |   |   |


**Шаг 4**: `l = 5`, `k = 2`, `T[5] = 3`

| l | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| P | x | y | x | y | x | z | x |
| T | 0 | 0 | 1 | 2 | 3 |   |   |


**Шаг 5**: `l = 6`, `k = 3`, `T[6] = 1`

| l | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| P | x | y | x | y | x | z | x |
| T | 0 | 0 | 1 | 2 | 3 | 1 |   |


**Шаг 6**: `l = 7`, `k = 1`, `T[7] = 1`

| l | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| P | x | y | x | y | x | z | x |
| T | 0 | 0 | 1 | 2 | 3 | 1 | 1 |

Теперь давайте рассмотрим пример реализации алгоритма KMP. 
У нас есть `P = {xyxyxzx}` из приведенного выше анализа. Предположим, что `S = {yxzyxyxyxyxzxxy}`. 
Теперь давайте пройдемся по алгоритму KMP, чтобы проверить, встречается ли `P` в `S`.


**Шаг 1**: `j = 1`, `i = 0`, сравниваем `P[1]` с `S[1]`. 
Т.к. `P[1]` не совпадает с `S[1]`, `P` сдвигается на одну позицию вправо.

Текст ~~y~~ x z y x y x y x y x z x x y

Шаблон ~~x~~ y x y x z x


**Шаг 2**: `j = 2`, `i = 0`, сравниваем `P[1]` с `S[2]`, есть совпадение.

Текст y **x** z y x y x y x y x z x x y

Шаблон **x** y x y x z x


**Шаг 3**: `j = 3`, `i = 1`, сравниваем `P[2]` с `S[3]`, нет совпадения.
Теперь, возвращаясь к `P` и сравнивая `P[1]` с `S[3]`, это не совпадение. 
Итак, теперь переходим к следующему символу в `S`, увеличив индекс до `S`.

Текст y x ~~z~~ y x y x y x y x z x x y

Шаблон x ~~y~~ x y x z x


**Шаг 4**: `j = 4`, `i = 0`, сравниваем `P[1]` с `S[4]`, нет совпадения. 
Затем двигаемся к следующему индексу `S`.

Текст y x z ~~y~~ x y x y x y x z x x y

Шаблон ~~x~~ y x y x z x


**Шаг 5**: `j = 5`, `i = 0`, сравниваем `P[1]` с `S[5]`, есть совпадение. 
Т.к. есть совпадение, то увеличиваем индекс `P` для следующего шага.

Текст y x z y **x** y x y x y x z x x y

Шаблон **x** y x y x z x


**Шаг 6**: `j = 6`, `i = 1`, сравниваем `P[2]` с `S[6]`, есть совпадение. 
Для следующего шага увеличиваем индекс `P`.

Текст y x z y **x** **y** x y x y x z x x y

Шаблон **x** **y** x y x z x


**Шаг 7**: `j = 7`, `i = 2`, сравниваем `P[3]` с `S[7]`, есть совпадение.
Для следующего шага увеличиваем индекс `P`.

Текст y x z y **x** **y** **x** y x y x z x x y

Шаблон **x** **y** **x** y x z x


**Шаг 8**: `j = 8`, `i = 3`, сравниваем `P[4]` с `S[8]`, есть совпадение.
Для следующего шага увеличиваем индекс `P`.

Текст y x z y **x** **y** **x** **y** x y x z x x y

Шаблон **x** **y** **x** **y** x z x


**Шаг 9**: `j = 9`, `i = 4`, сравниваем `P[5]` с `S[9]`, есть совпадение.
Для следующего шага увеличиваем индекс `P`.

Текст y x z y **x** **y** **x** **y** **x** y x z x x y

Шаблон **x** **y** **x** **y** **x** z x


**Шаг 10**: `j = 10`, `i = 5`, сравниваем `P[6]` с `S[10]`, совпадений нет. 
Поэтому возвращаемся к `P` и сравниваем `P[4]` с `S[10]`, так как несоответствие привело к `i = prefixValue[5] = 3`. 
См. этапы вычисления префикса выше. 
Поскольку есть совпадение, также увеличиваем индекс P для следующего шага.

Текст y x z y **x** **y** **x** **y** **x** ~~y~~ x z x x y

Шаблон **x** **y** **x** **y** **x** ~~z~~ x


**Шаг 11**: `j = 11`, `i = 4`, сравниваем `P[5]` с `S[11]`, есть совпадение. 
Поскольку совпадение есть, увеличиваем индекс `P` для следующего шага. 

Текст y x z y x y **x** **y** **x** **y** **x** z x x y

Шаблон **x** **y** **x** **y** **x** z x 


**Шаг 12**: `j = 12`, `i = 5`, сравниваем `P[6]` с `S[12]`, есть совпадение. 
Увеличиваем индекс `P` для следующего шага. 

Текст y x z y x y **x** **y** **x** **y** **x** **z** x x y

Шаблон **x** **y** **x** **y** **x** **z** x


**Шаг 13**: `j = 13`, `i = 6`, сравниваем `P[7]` с `S[13]`. Есть совпадение. 
Поскольку у нас больше не осталось символов в `P`, это завершает процесс, 
и мы можем вернуть значение индекса, `value = currentIndex(S) + 1 − length(P) = 14 − 7 = 7`. 

В этом примере общее количество сдвигов = `i − m = 13 − 7 = 6`. 

Текст y x z y x y **x** **y** **x** **y** **x** **z** **x** x y

Шаблон **x** **y** **x** **y** **x** **z** **x**

**Оценка:**

- **Время** - ???
- **Память** - ???

**Код:**

```dotty
def kmpSubstringSearch(searchWord: String, source: String): Int = {
  val prefixTab = prefixTable(searchWord)
  source.indices
    .foldLeft((-1, 0)) {
      case ((foundIndex, _), _) if foundIndex > 0 => (foundIndex, 0)
      case ((_, x), i) =>
        val stepsX = LazyList.iterate(x)(x => prefixTab(x - 1))
        val lowerX =
          stepsX
            .find(x => x == 0 || searchWord(x) == source(i))
            .getOrElse(0)
        val newX =
          if searchWord(lowerX) == source(i) then lowerX + 1
          else lowerX
        if newX == searchWord.length then (i - newX + 1, 0)
        else (-1, newX)
    }
    ._1
}

private def prefixTable(searchString: String): Vector[Int] =
  searchString.tail
    .foldLeft((0, Vector(0))) { case ((initialValue, prefixT), currentCharacter) =>
      val lowerValue =
        LazyList
          .iterate(initialValue)(initialValue => prefixT(initialValue - 1))
          .find(initialValue => initialValue == 0 || searchString(initialValue) == currentCharacter)
          .getOrElse(0)
      val newValue =
        if searchString(lowerValue) == currentCharacter then lowerValue + 1
        else lowerValue
      (newValue, prefixT :+ newValue)
    }
    ._2
```

**Метрики:**

Поиск подстроки в 100 символов в тексте в миллион символов занимает 0,3 секунды.

```dotty
private val source: String = Random.nextString(1_000_000)
private val searchWord: String = source.takeRight(100)

@main def searchBench(): Unit =
  println(naiveSubstringSearch(searchWord, source))
  println(kmpSubstringSearch(searchWord, source))
      
// CPU Time: 301 ms
// Allocation memory size: 346,34 MB      
```

---

**Ссылки:**

- [Bhim P. Upadhyaya - Data Structures and Algorithms with Scala](https://link.springer.com/book/10.1007/978-3-030-12561-5)
- [Scalacaster - Search algorithms](https://github.com/vkostyukov/scalacaster/tree/master/src/search)
